package 构建前缀信息的技巧_解决子数组相关问题;

import java.util.HashMap;

// 表现良好的最长时间段
// 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数
// 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是 劳累的一天
// 所谓 表现良好的时间段 ，意味在这段时间内，「劳累的天数」是严格 大于 不劳累的天数
// 请你返回 表现良好时间段 的最大长度
// 测试链接 : https://leetcode.cn/problems/longest-well-performing-interval/
public class Code05_LongestWellPerformingInterval {

    public int longestWPI(int[] hours) {
        // 纪录：某个前缀和，最早出现的位置
        HashMap<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        // 0这个前缀和，最早出现在-1位置，一个数也没有的时候
        map.put(0, -1);
        for(int i = 0, sum = 0; i < hours.length; i++){
            sum += hours[i] > 8 ? 1 : -1;
            if(sum > 0){
                // 说明此时工作时间大于8个小时的天数是大于工作时间小于8个小时的天数
                ans = i+1;
            }else {
                // sum <= 0
                if(map.containsKey(sum-1)){
                    ans = Math.max(ans, i - map.get(sum-1));
                }
            }
            if(!map.containsKey(sum)){
                map.put(sum, i);
            }
        }
        return ans;
    }
}
